class Solution {
public:
    int trap(vector<int>& height) {
        vector<int> stack({ 0 });   // 数组作栈
        int res = 0, left = height[stack[0]], index = 0;
        for (int i = 1; i < height.size(); ++i) {
            if (stack.size() == 1) {
                left = height[stack[0]];
            }
            //
            index = i;
            while (stack.size() and height[i] > height[*stack.rbegin()]) {
                if (index - *stack.rbegin() > 1) {
                    res += (index - *stack.rbegin() - 1) * (min(left, height[i]) - height[index]);
                }
                res += min(left, height[i]) - height[*stack.rbegin()];
                index = *stack.rbegin();
                stack.pop_back();
            }
            if (stack.size() and index - *stack.rbegin() > 1) {
                res += (index - *stack.rbegin() - 1) * (min(left, height[i]) - height[index]);
            }
            stack.push_back(i);

        }
        return res;
    }
};